package q765_minSwapsCouples;

public class Solution_1 {
    /*
    贪心的交换
    从图的角度来讲，将N对情侣看做图中的 N 个节点；
    对于每对相邻的位置，如果是第i对与第j对坐在了一起，则在i号节点与j号节点之间连接一条边，
    代表需要交换这两对情侣的位置。
    因为这题情侣是2人一对，同一连通分量内，每个点最多连出两条边，且必成环
    （可以用反证法；当连通分量内只有一个点时，说明该情侣坐对了，不需要换位置；
    只有两个点时，图中只有一条边，直接调换一次即可；
    在一般情况下，即连通分量内点数大于2时，
    此时每个点必须连出两条边[如果只连一条边的话，一定属于第二种只有两个点的情况；
    连三条边不可能，因为情侣是2人]！这一条件当且仅当成环的时候成立，
    反之会出现某些点只有一条边或者多余两条边的情况）。
    ===至此，对于每个连通分量，由于其一定成环，
    所以我们直接沿着环的方向依次交换（边数-1）次即可使得该连通分量内情侣牵手，也就是贪心交换。
     */
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] indexMap = new int[n]; // 索引表，row[i] = num => index[num] = i
        for (int i = 0; i < n; i++) {
            indexMap[row[i]] = i;
        }
        int count = 0;
        for (int i = 0; i < n - 1; i += 2) {
            int p1 = row[i];
            int p2 = (p1 & 1) == 0 ? p1 + 1 : p1 - 1; // p1的情侣
            if (row[i + 1] == p2) continue; // p1和p2正好挨着，无需交换这一对
            int p2Index = indexMap[p2]; // p2的位置
            swap(row, indexMap, i + 1, p2Index); // 交换 p2 <=> [i+1]
            count++;
        }
        return count;
    }

    // 这里的swap在交换两个情侣的时候 还需要维护indexMap
    private static void swap(int[] row, int[] indexMap, int i, int j) {
        int tmp = row[i];
        row[i] = row[j];
        row[j] = tmp;
        indexMap[row[i]] = i;
        indexMap[row[j]] = j;
    }
}
